Оглавление

Введение…2

Постановка задачи…3

Решение игры при n=3…3

Решение игры при n=7…7

Заключение.10

Список литературы 11

Внимание!

Это ОЗНАКОМИТЕЛЬНАЯ ВЕРСИЯ работы №3649, цена оригинала 1000 рублей. Оформлена в программе Microsoft Word.

Оплата. Контакты.

Введение

В задачах управления мобильными интеллектуальными роботами весьма часто возникают ситуации, при которых планирование действий объекта системы зависит от порядка или характера действий другого робота или иного объекта, вступающего в конфликтное взаимодействие с первым. Объекты представленной системы могут принимать решения, иметь свои часто представленные с некоторой долей вероятности интересы, что довольно сильно усложняет процесс выбора оптимальной стратегии управления роботом. Для упрощения решения проблем управления, определения выгодных стратегий действий роботов используют методы, представленные математической теорией конфликтных ситуаций – теорией игр. Подобная формализация позволяет смоделировать процесс и прогнозировать результаты игры, что делает возможным определения целесообразных и эффективных стратегий. Оптимальный выбор модели управления мобильным роботом, в свою очередь, является

определяющим фактором достижения результата.

В настоящей курсовой работе представлено решение задачи распределения усилий на атаку и защиту объектов. Решение проводится при двух вариантах исходных данных. Целью настоящей курсовой работы является приобретение базового опыта решения матричных игр.

Мобильный робот I (МР-1) атакует n объектов стоимостями b, (i=1, 2,, n),

мобильный робот II (МР-2) охраняет. МР-1 и МР-2 могут атаковать и защищать по одному объекту. i-й неохраняемый объект МР-1 может поразить с вероятностью pi, охраняемый — с вероятностью 1-р.

1) Составить модель игры при n=3 и решить ее.

2) Составить модель игры при n=7 и решить, преобразовав ее в задачу линейного программирования.

Исходные данные:

a) n=3, bi=2, p=0.8, pi=0.9;

б) n=7, bi=4, p=0.9, pi=0.9;

Ход решения:

1) Составить модель игры при n=3

Мобильный робот I (МР-1) атакует 3 объекта стоимостями bi=2,

мобильный робот II (МР-2) охраняет. МР-1 и МР-1 могут атаковать и защищать по одному объекту. i-й неохраняемый объект МР-1 может поразить с вероятностью 0.9, охраняемый — с вероятностью 1-0.8. На основании этих данных можно составить таблицу. (таблица 1).

Составляем игровую матрицу A1, учитывая цену объектов (bi=2).

Где строки являются стратегиями стороны — А, а столбцы стратегиями стороны — В.

Проверяем на наличие седловой точки:

А1=0.4, А2=0.4, А3=0.4;

В1=1.8, В2=1.8, В3=1.8;

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 0.4, которая указывает на максимальную чистую стратегию A1.

Верхняя цена игры b = min(bj) = 1.8.

Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 0.4 ≤ v ≤ 1.8. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

В платежной матрице отсутствуют доминирующие строки.

В платежной матрице отсутствуют доминирующие столбцы.

Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш.

Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.

Цель игрока 1 получить максимальную выручку от атаки. выручка, представляется общей стоимостью пораженных роботов

Находим решение игры в смешанных стратегиях.

Запишем систему уравнений.

Для игрока I

0.4p1+1.8p2+1.8p3 = v

1.8p1+0.4p2+1.8p3 = v

1.8p1+1.8p2+0.4p3 = v

p1+p2+p3 = 1

Для игрока II

0.4q1+1.8q2+1.8q3 = v

1.8q1+0.4q2+1.8q3 = v

1.8q1+1.8q2+0.4q3 = v

q1+q2+q3 = 1

Решая эти системы методом Гаусса, находим:

v = 1.3333333

p1 = 0.3333333(вероятность применения 1-ой стратегии).

p2 = 0.3333333(вероятность применения 2-ой стратегии).

p3 = 0.3333333(вероятность применения 3-ой стратегии).

Оптимальная смешанная стратегия игрока I: P = (0.3333333; 0.3333333; 0.3333333)

q1 = 0.3333333 (вероятность применения 1-ой стратегии).

q2 = 0.3333333 (вероятность применения 2-ой стратегии).

q3 = 0.3333333 (вероятность применения 3-ой стратегии).

Оптимальная смешанная стратегия игрока II: Q = (0.3333333; 0.3333333; 0.3333333)

Цена игры: v= 1.3333333

2) Составление модели игры при n=7. Решение методом линейного программирования.

n=7, bi=4, p=0.9, pi=0.9;

Мобильный робот I (МР-1) атакует 7 объекта стоимостями bi=4,

мобильный робот II (МР-2) охраняет. МР-1 и МР-1 могут атаковать и защищать по одному объекту. i-й неохраняемый объект МР-1 может поразить с вероятностью 0.9, охраняемый — с вероятностью 1-0.9.

Игровая матрица при n=7 выглядит следующим образом:

0.4 3.6 3.6 3.6 3.6 3.6 3.6

3.6 0.4 3.6 3.6 3.6 3.6 3.6

3.6 3.6 0.4 3.6 3.6 3.6 3.6

3.6 3.6 3.6 0.4 3.6 3.6 3.6

3.6 3.6 3.6 3.6 0.4 3.6 3.6

3.6 3.6 3.6 3.6 3.6 0.4 3.6

3.6 3.6 3.6 3.6 3.6 3.6 0.4

При решении задач большей размерности целесообразно использовании методов линейного программирования. Тогда возникает необходимость представления игровой ситуации в виде, удобном для расчета.

Пусть цена игры V>0. Для этого достаточно, чтобы для каждого элемента платежной матрицы aij выполнялось неравенство aij>0.

При решении игровых задач методами линейного программирования необходимо представить данные условия в удобном для расчета виде:

Пусть игрок I принимает только оптимальную стратегию, а игрок II только чистые стратегии.

{█(0.4x_1+3.6x_2+3.6x_3+3.6x_4+3.6x_5+3.6x_6+3.6x_7≥v@3.6x_1+0.4x_2+3.6x_3+3.6x_4+3.6x_5+3.6x_6+3.6x_7≥v@3.6x_1+3.6x_2+0.4x_3+3.6x_4+3.6x_5+3.6x_6+3.6x_7≥v@3.6x_1+3.6x_2+3.6x_3+0.4x_4+3.6x_5+3.6x_6+3.6x_7≥v@3.6x_1+3.6x_2+3.6x_3+3.6x_4+0.4x_5+3.6x_6+3.6x_7≥v@3.6x_1+3.6x_2+3.6x_3+3.6x_4+3.6x_5+0.4x_6+3.6x_7≥v@3.6x_1+3.6x_2+3.6x_3+3.6x_4+3.6x_5+3.6x_6+0.4x_7≥v)┤

Пусть

x_i/v=z_i

Тогда для первого игрока:

{█(0.4z_1+3.6z_2+3.6z_3+3.6z_4+3.6z_5+3.6z_6+3.6z_7≥1@3.6z_1+0.4z_2+3.6z_3+3.6z_4+3.6z_5+3.6z_6+3.6z_7≥1@3.6z_1+3.6z_2+0.4z_3+3.6z_4+3.6z_5+3.6z_6+3.6z_7≥1@3.6z_1+3.6z_2+3.6z_3+0.4z_4+3.6z_5+3.6z_6+3.6z_7≥1@3.6z_1+3.6z_2+3.6z_3+3.6z_4+0.4z_5+3.6z_6+3.6z_7≥1@3.6z_1+3.6z_2+3.6z_3+3.6z_4+3.6z_5+0.4z_6+3.6z_7≥1@3.6z_1+3.6z_2+3.6z_3+3.6z_4+3.6z_5+3.6z_6+0.4z_7≥1)┤

Первый игрок стремиться сделать свой выигрыш максимальным (минимизировать проигрыш min 1/v).

Для второго игрока также можно составить неравенства, определяющие цену игры:

{█(0.4y_1+3.6y_2+3.6y_3+3.6y_4+3.6y_5+3.6y_6+3.6y_7≤v@3.6y_1+0.4y_2+3.6y_3+3.6y_4+3.6y_5+3.6y_6+3.6y_7≤v@3.6y_1+3.6y_2+0.4y_3+3.6y_4+3.6y_5+3.6y_6+3.6y_7≤v@3.6y_1+3.6y_2+3.6y_3+0.4y_4+3.6y_5+3.6y_6+3.6y_7≤v@3.6y_1+3.6y_2+3.6y_3+3.6y_4+0.4y_5+3.6y_6+3.6y_7≤v@3.6y_1+3.6y_2+3.6y_3+3.6y_4+3.6y_5+0.4y_6+3.6y_7≤v@3.6y_1+3.6y_2+3.6y_3+3.6y_4+3.6y_5+3.6y_6+0.4y_7≤v)┤

В случае если совершить замену:

y_i/v=w_i

{█(0.4w_1+3.6w_2+3.6w_3+3.6w_4+3.6w_5+3.6w_6+3.6w_7≤1@3.6w_1+0.4w_2+3.6w_3+3.6w_4+3.6w_5+3.6w_6+3.6w_7≤1@3.6w_1+3.6w_2+0.4w_3+3.6w_4+3.6w_5+3.6w_6+3.6w_7≤1@3.6w_1+3.6w_2+3.6w_3+0.4w_4+3.6w_5+3.6w_6+3.6w_7≤1@3.6w_1+3.6w_2+3.6w_3+3.6w_4+0.4w_5+3.6w_6+3.6w_7≤1@3.6w_1+3.6w_2+3.6w_3+3.6w_4+3.6w_5+0.4w_6+3.6w_7≤1@3.6w_1+3.6w_2+3.6w_3+3.6w_4+3.6w_5+3.6w_6+0.4w_7≤1)┤

Второй игрок стремиться сделать свой проигрыш минимальным (max 1/v).

Для решения поставленной задачи была использована среда Matlab 2010b. Библиотеки среды содержат функцию (linprog()) для решения задач линейного программирования. С помощью них можно определить оптимальные стратегии для первого и второго игрока.

Для заданной игры вектор w принимает значение:

w=[0.0455; 0.0455; 0.0455; 0.0455; 0.0455; 0.0455; 0.0455; ]Т

Для заданной игры вектор z принимает значение:

z=[0.0455; 0.0455; 0.0455; 0.0455; 0.0455; 0.0455; 0.0455; ]Т

Цена игры равна: v=[3.1429]

Исходя из равенства x=v*w, можно определить стратегии первого игрока:

x = [0.1429; 0.1429; 0.1429; 0.1429; 0.1429; 0.1429; 0.1429; ]Т

Исходя из равенства y=v*z, можно определить стратегии второго игрока:

y= [0.1429; 0.1429; 0.1429; 0.1429; 0.1429; 0.1429; 0.1429; ]Т

Заключение

Одним из основополагающих этапов синтеза модели управления мобильными интеллектуальными роботами является разработка аппарата принятия решений и планирование действий. Нередко данный вопрос осложнен ввиду наличия конфликтных ситуаций в среде функционирования. Методы теории игр позволяют описать создавшиеся ситуации и успешно прогнозировать результаты выбора возможных действий агента системы.

В рамках выполнения настоящей курсовой работы были получен базовый опыт и отработаны навыки составления матричных игр на основе представленных заданием игровых ситуаций, определены оптимальные стратегии игроков аналитическим методами, исследован и отработан метод сведения матричной игры к задаче линейного программирования.

Список литературы:

Колобашкина Л.В., Основы теории игр. – М.: Изд-во Бином, 2011. – 162 с.

Дрешер М., Стратегические игры. Теория и приложения. – Советское радио, 1964. – 352 с.

Мак Кинси Дж., Введение в теорию игр. — М.: Физматлит, 1960. — 420 с.

Приложение

Листинг программы Matlab для решения матричной игры mxn:

>> [w, fval] = linprog( ones(7, 1), -A’, -ones(7,1), [],[], zeros(7,1));

Optimization terminated.

>> [z, gval] = linprog( -ones(7, 1), A, ones(7,1), [],[], zeros(7,1));

Optimization terminated.

>> v=1/fval;

>> y=v*z;

>> x=v*w;